           2. (La SHOP la Slatina). La un SHOP din Slatina se gasesc spre
vnzare p-1 (p prim) produse unicat de costuri x(1), x(2),...,x(p-1) (sumele
sunt date n dolari $). Nici unul dintre produse nu poate fi cumparat prin
plata exacta cu bancnote de p$. In SHOP intra un olimpic care are un numar
nelimitat de bancnote de p$ si o singura bancnota de q$, (1qp-1). Ce produse
trebuie sa cumpere olimpicul pentru a putea plati exact produsele cumparate ?
Restrictii tehnice:
    Datele de intrare se dau n fisierul de intrare ce contine doua linii:
- pe prima linie valorile lui p si q;
- pe a doua linie valorile costurilor produselor.
    Solutia se va afisa pe monitor.
Exemplu: Pentru fisierul de intrare:
5 4
1 3 6 7
o solutie este:
1 3
=================================
Solutie: (Mihai Stroe)
  Problema se rezolva folosind principiul lui Dirichlet.
  Pastram costurile in vectorul a.
  Calculam sumele: s[1]=a[1];
                   s[2]=a[1]+a[2];
                   s[3]=a[1]+a[2]+a[3];
                   ..................
                   s[i]=a[1]+...+a[i];
                   ..................
                   s[p-1]=a[1]+a[2]+...+a[p-1].
  Daca printre resturile care se obtin impartind fiecare suma la p se
  afla resturile 0 sau q, atunci problema admite ca solutie produsele 1..q.
  Altfel, exista doua resturi cu aceeasi valoare; sa notam cu s[i] si s[j]
  sumele pentru care ele au fost obtinute,j<i.
  In situatia aceasta:s[i]>s[j];s[i]=m*p+r,s[j]=n*p+r => s[i]=s[j]=p*(m-n)
  care este multiplu de p si problema admite solutie produsele j+1,j+2,...,i.
  Principiul lui Dirichlet se aplica in varianta standard pe p saci, dar fara
  folosirea monedei q; el poate fi generalizat pe mai putini saci,dar folosind
  mai multe tipuri de monede.

uses crt;
var nr,a,s:array[0..1000]of longint;
    luate:set of byte;
    f:text;
    i,j,k,l,m,n,p,q:integer;
    ss:string;

begin
  write('Introduceti numele fisierului de intrare ');
  readln(ss);
  assign(f,ss);
  reset(f);
  readln(f,p,q);
  for i:=1 to p-1 do
      begin
        read(f,a[i]);
        s[i]:=s[i-1]+a[i];
      end;
  close(f);
  for i:=1 to p-1 do
      if (s[i] mod p=0)or(s[i] mod p=q) then
            begin
              for j:=1 to i do write(a[j],' ');
              writeln;
              repeat until keypressed;
              halt;
            end
            else
            begin
              if s[i] mod p in luate then
                 begin
                 for j:=nr[s[i]mod p]+1 to i do write(a[j],' ');
                 writeln;
                 repeat until keypressed;
                 halt;
               end;
              luate:=luate+[s[i]mod p];
              nr[s[i]mod p]:=i;
            end;
end.
